import java.util.*;

public class levelOrderBottom {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode, Integer> map = new HashMap<>();
        map.put(root, 1);
        int curLevel = 1;
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (map.get(node) != curLevel) {
                ans.add(new ArrayList<>(list));
                curLevel++;
                list.clear();
            }
            list.add(node.val);
            if (node.left != null) {
                map.put(node.left, curLevel + 1);
                queue.add(node.left);
            }
            if (node.right != null) {
                map.put(node.right, curLevel + 1);
                queue.add(node.right);
            }
        }
        ans.add(new ArrayList<>(list));
        Collections.reverse(ans);
        return ans;
    }
}
